package exercise;

import java.util.ArrayList;
import java.util.List;

// https://leetcode.cn/problems/combination-sum-iii/
public class L230702_II {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();

        dfs(ans, cur, k, n, 0, 1);
        return ans;
    }

    private void dfs(List<List<Integer>> ans, List<Integer> cur, int k, int n, int sum, int pos) {
        // 当下一个元素相加和大于 n, 剪枝
        if (sum > n) {
            return;
        }
        // 找到一个答案, 添加到 ans 里
        if (n == sum && cur.size() == k) {
            ans.add(new ArrayList<>(cur));
            return;
        }

        for (int i = pos; i < 10; i++) {
            cur.add(i);
            if (pos <= i) {
                pos = i + 1;
            }
            dfs(ans, cur, k, n, sum+i, pos);
            pos--;
            cur.remove(cur.size()-1);
        }
    }

    public static void main(String[] args) {
        L230702_II s = new L230702_II();
        System.out.println(s.combinationSum3(3, 10));
    }
}
